
#include <stdlib.h>
#include <stdio.h>
#include <string.h> // C string, not C++ string
#include <queue>
#include <vector>

#include "graph.h"
#include "auxiliares-grasp.h"



void imprimirDijkstraInterno(vector<float> *v);
/**
 * Encuentra los k caminos mas cortos entre los nodos inicio y fin
 * @param G grafo en el que se busca el camino mas corto
 * @param inicio
 * @param fin
 * @param k cantidad de caminos a encontrar
 * @param d cantidad de saltos maximo entre inicio y fin
 */
int** Yen(Graph * G, int inicio, int fin, int k, int d) {
    typedef std::priority_queue<int*, vector<int*>, mycomparison> ColaPrioridad;

    int ** A = new int*[k];
//    A[0] = Dijstra(G, inicio, fin);
//    // int** B;
//    ColaPrioridad B;
//
//    for (int rr = 0; rr < k; rr++) {
//        for (int i = 0; i < tam_aux(A); i++) { //for i from 0 to size(A[k − 1]) − 1:
//            int spurNode = A[rr - 1][i];
//            int* rootPath = A[rr - 1]; //FIXME sacar nodos luego de i
//
//            for (;;) {//FIXME controlar como vamos a iterar
//                int* p; //path del for each
//                if (pathIguales(rootPath, p)) {
//                    //TODO borramos la arista (i,i+1) de el grafo G
//                }
//            }
//            int* spurPath = Dijstra(G, spurNode, fin);
//
//            //uno los caminos
//            int* totalPath = unirPath(rootPath, spurPath);
//            if (costo(totalPath) <= d) {
//                //se lo agregamos a B
//                B.push(totalPath);
//            }
//
//            // TODO restauramos G
//        }
//        //sacamos el elemento en B con menor costo y lo metemos en A en la pos rr
//        if (!B.empty()) {
//            A[rr] = B.top();
//            B.pop();
//        }
//    }
    return A;
};





// Devuelve un vector con las distancias del nodo inicial al resto de los vertices.
// Guarda en path los nodos que forman el camino mínimo y muestra la cantidad de caminos posibles

vector<float>* dijkstra(Graph* g, int inicial, int final) {
    vector<float>* ptrDist = new vector<float>;
    vector<float> distancias=*ptrDist;
    list<int> noVisitados;

    int infinito = -1;
    int caminosPosibles = 0;

    // Declaraciones en el archivo .h
    int cn = g->getTamanio(); //cantidad de nodos
    float** ady= g->getCostos(); //matriz de adyacencia, COSTOS
    deque<int> path; // camino mínimo de dijkstra


    //decremento para manejarme en [0, cn)
    // Seteo las distancias en infinito y marco todos los nodos como no visitados
    for (int i = 0; i < cn; i++) {
        distancias.push_back(infinito);
        noVisitados.push_back(i);
    }

    // Actual es el nodo inicial y la distancia a si mismo es 0
    int actual = inicial;
    distancias[inicial] = 0;

    // Inicializo el camino mínimo en infinito.
    path = deque<int>(cn, infinito);

    while (!noVisitados.empty()) {
        // Para cada nodo no visitado, calculo la distancia tentativa al nodo actual;
        // si es menor que la distancia seteada, la sobreescribo.
        for (list<int>::iterator itList = noVisitados.begin(); itList != noVisitados.end(); itList++) {
            // distancia tentativa = distancia del inicial al actual + distancia del actual al noVisitado
            int dt = distancias[actual] + ady[actual][*itList];
            if (distancias[*itList] > dt) {

                // Agrego a camino el nodo (actual) a través del cual el nodo inicial se conecta con *itList
                path[*itList] = actual;
            } else if (distancias[*itList] == dt && *itList == final)
                caminosPosibles++;

        }
        // Marco como visitado el nodo actual, la distancia seteada es la mínima.
        noVisitados.remove(actual);

        // Si no lo pase como parámetro final vale -1, en ese caso el if nunca da true.
        if (actual == final) break;

        // El nodo actual ahora es el nodo no visitado que tiene la menor distancia al nodo inicial.
        int min = infinito;
        for (list<int>::iterator itList = noVisitados.begin(); itList != noVisitados.end(); itList++)
            if (min >= distancias[*itList]) {
                min = distancias[*itList];
                actual = *itList;
            }
    }

    // Si final vino como parámetro obtengo el camino mínimo y lo guardo en path
    if (final != -1) {
        deque<int> temp;
        int nodo = final;

        while (nodo != inicial) {
            temp.push_front(nodo);
            nodo = path[nodo];
        }

        path = temp;

        if (ady[inicial][final] != infinito)
            caminosPosibles++;

        cout << "Caminos Posibles " << caminosPosibles << endl;
    }
    imprimirDijkstraInterno(ptrDist);
    imprimirDijkstraInterno(&distancias);
    return ptrDist;
};


void imprimirDijkstraInterno(vector<float> *v){
	cout << "Probando Dijkstra Inerno" << endl;
	for(vector<float>::iterator it=v->begin(); it!=v->end(); it++){
		cout << "\t" << *it << endl;
	}
	cout << "Fin camino Dijkstra" << endl;
}